package com.dycong.common.leetcode;

import com.dycong.common.leetcode.ds.ListNode;

/**
 * @author dycong
 * @date 2019/10/29 9:08
 * <p>
 * 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 1->2->3->4->5->NULL, k = 2
 * 输出: 4->5->1->2->3->NULL
 * 解释:
 * 向右旋转 1 步: 5->1->2->3->4->NULL
 * 向右旋转 2 步: 4->5->1->2->3->NULL
 * 示例 2:
 * <p>
 * 输入: 0->1->2->NULL, k = 4
 * 输出: 2->0->1->NULL
 * 解释:
 * 向右旋转 1 步: 2->0->1->NULL
 * 向右旋转 2 步: 1->2->0->NULL
 * 向右旋转 3 步: 0->1->2->NULL
 * 向右旋转 4 步: 2->0->1->NULL
 * 题解
 * 昨晚吃火锅吃撑了回来这道题，还算顺利~~
 * 链表的题目,其实就是在考指针交换,这个题目先让链表连成一个环，然后再切开就可以完成了。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/rotate-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class RotateRight_61 {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode cur = head;
        for (int i = 2; i <= 5; i++) {
            cur.next = new ListNode(i);
            cur = cur.next;
        }
        System.out.println(ListNode.format(head));
        head = rotateRight(head, 2);
        System.out.println(ListNode.format(head));
    }

    public static ListNode rotateRight(ListNode head, int k) {

        if (head == null || head.next == null) {
            return head;
        }

        int count = 1;
        ListNode cur = head;

        while (cur.next != null) {
            count++;
            cur = cur.next;
        }
        //此时,count 为单链表节点数，cur 为最后一个节点
        // k 假如是 count 倍数，则无翻转，同时防止 k>count 溢出
        k = k % count;
        if (k == 0) {
            return head;
        }

        //建造环
        cur.next = head;
        //虚拟节点
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        dummy.next = head;
        ListNode pre = dummy;
        for (int i = 0; i < count - k; i++) {
            pre = pre.next;
        }

        //释放虚拟节点,并不需要
        dummy.next = null;

        //需要返回的是pre的next，其才是新的头结点
        cur = pre.next;
        pre.next = null;
        return cur;
    }


}
